/**
 * @param {string} s
 * @return {number}
 */
 var countSubstrings = function(s) {
  // dp[i][j] 表示在区间i~j范围内 左闭右闭区间内 是不是会问字符串
  // 递推公式 如果 s[i] !== s[j] 那么这个肯定就不是回文字符串 
  // 如果s[i] === s[j] 如果两个是一个字符串 那么肯定是回文字符串
  // 如果 两个相差1 那么也是回文字符串
  // 如果 两个相差大于1 那么需要看i+1,j-1范围内是不是回文字符串了 如果是 那这个就是
  // 初始化 所有节点在一开始的时候就都初始化为false
  // 遍历顺序 我们要panduani+1,j-1 这个位置是在要计算的左下角 那么需要从地下到上面 从左到右
  let dp = new Array(s.length).fill(0).map(()=>new Array(s.length).fill(false))
  let result = 0
  for(let i = s.length-1;i >= 0;i--){ // 从下到上 i代表第一个
    for(let j = i;j < s.length;j++){ // 从左到右 j代表第二个 第二个要在第一个和结束之间
      if(s[i] === s[j]){
        // 如果两个数字相同 判断两个的位置差是不是小于等于1
        if(j-i <= 1){ // 如果两者相差1位以内
          result++ // 结果+1
          dp[i][j] = true // 此时的dpdp[j][i]是真
        }else{
          if(dp[i+1][j-1]){
            // 如果这个j+1和i-1的是真 就是真
            result++
            dp[i][j] = true
          }
        }
      }
    }
  }
  return result
};




/**
 * @param {string} s
 * @return {number}
 */
 var countSubstrings = function(s) {
    // 双指针法
    // 遍历这个字符串
    let strLen = s.length // 获得字符串的长度
    let result = 0 // 结果初始化为0
    for(let i = 0;i < 2 * strLen - 1;i++){
      // 从第一个一直到最后 2*strlen-1 是为了让这个i/2落在这个长度内
      let left = Math.floor(i / 2) // 获得这个的左节点 i / 2是什么 是这个的一半
      let right = left + i % 2 // 获得这个左节点的右边的节点 就是这个的有边界 如果是i是偶数 nameleft 就是right 如果是奇数 left = right - 1
      while(left >= 0 && right < strLen && s[left] === s[right]){
        // 只要是左边大于等于0  右边小于这个的长度 并且左边的字母和右边的字母是相等的
        result++ // 结果就加一
        left-- // 左边界扩张
        right++ // 有边界扩张
      }
    }
    return result
};